Deadlock Detection死結的偵測

(1)系統中可能存在Deadlock(if prevention and avoidance)不用偵測死結是否存在，若死結存在，則必須打破死 結，恢復正常的機制。

(2)優點：resource utilization較高，Throughput↑
缺點：cost太高

Deadlock detection algorithm

定義:

1.Available[1..m] 表系統目前可用資源數量

2.Allocation[1..n,1..m] 各process目前所持有的資源量

3.Request[1..n,1..m] 表示目前各process所提出的各類資源申請數量

4.Work[1..m] 目前可用資源數量之累計

5.Finish[1..n] of boolean
Finish[i] = false：尚未完成且Allocation!=0

          trun：已完成

判斷:

Steps:

1.設定初值

Work = Available
Finish[i] = false, if Allocation != 0

       true, otherwise

2.找到Pi滿足

Finish[i]=false

Requesti≤Work

若找到，則goto 3 ，否則 goto 4

3.設定Finish[i]=true 且 Work = Work + Allocationi goto 2

4.檢查Finish鎮列，若皆為true，則表示system無死結存在
否則，Deadlock存在 (且那些Finish[i]為false的processes陷入死結)

死結的恢復

一旦檢測出死結，則就要採取一些策略使系統從死結中恢復，常有以下方法來從死結中恢復:

(1)結束所有死結進程。即強制性地從系統中撤銷死結進程，並剝奪它們的資源給剩下的進程使用。（使前面的工作全部 損失）

(2)將死結進程退回到前一個檢查點，並重新從該檢查點啓動這些進程（前提是系統必須提供檢查點和重新啓動的機 制）。

(3)相繼的逐個結束死結進程直至死結不再存在。在每個進程結束後，都要使用死結檢測算法以確定死結是否依然存在。

(4)相繼的逐個搶佔死結進程的資源，直至死結不再存在。但搶佔資源的方法是否可行，往往與資源特性有關。有時搶佔 資源還需要人工干預，例如搶佔激光印表機時就需將原來影印的紙張先放到一邊去，並使被搶佔進程回到當初獲得資 源時的斷點。

由於所有使死結進程相繼結束和強佔資源策略均涉及損失了這些進程已完成工作的開銷。因此要基於成本的基礎上選擇結束進程的次序。首先要優先選擇以下死結進程：

1.選擇使用最少處理器時間的進程。

2.選擇使用最少輸出工作量的進程。

3.選擇具有最多剩餘時間的進程。

4.選擇分的最少資源進程。

5.具有最小優先級的進程。